package bintree.heap.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 最小的K个数
 * @author yuisama
 **/

class  IntegerReverse implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
  }
public class Num1714取出前K个元素 {
    public int[] smallestK(int[] arr, int k) {
//        Arrays.sort(arr);
//        Arrays.copyOf(arr,k);
        int[] ret = new int[k];
        if (arr.length == 0||k ==0){
            return ret;
        }
        //JDK默认是最小堆，需要改成一个最大堆
        //Lambda表达式
//        Queue<Integer> queue = new PriorityQueue<>((o1,o2) -> o2 - o1);
//        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2-o1;
//            }
//        });
       Queue<Integer> queue = new PriorityQueue<>(new IntegerReverse());
        // 遍历原集合，队列只保存k个元素
        for (int i = 0; i < arr.length; i++) {
            if (queue.size()<k){
                queue.offer(arr[i]);
            }else {
                int max = queue.peek();
                if (arr[i]< queue.peek()){
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
        int i = 0;
        while (!queue.isEmpty()){
            ret[i++] = queue.poll();
        }
        return ret;
    }
}
